<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>恰好移动 k 步到达某一位置的方法数目</title>
</head>
<body>
  <script>
    function fn(startPos, endPos, k) {
      const MOD = 1e9 + 7;
      // 记忆化
      const cache = new Map();
      // 递归调用函数，求当前pos恰好移动step步到达endPos的结果数
      function getNum(pos, step) {
        const key = `${pos},${step}`;
        if (cache.has(key)) return cache.get(key);
        // 递归终止条件: 相隔终点距离大于剩余步数
        if (Math.abs(pos - endPos) > step) return 0
        // 递归终止条件: 步数走完，算一种方案，这里pos一定等于endPos 否则就被上面条件终止了
        if (step === 0) return 1;
        // 俩种方案
        const prev = getNum(pos - 1, step - 1);
        const next = getNum(pos + 1, step - 1);
        const sum = (prev + next) % MOD;
        cache.set(key, sum);
        return sum;
      }

      return getNum(startPos, k)
    }
    console.log(fn(1, 2, 3))
  </script>
</body>
</html>